package hard

/*
时间复杂度:O(n^3) 三层循环
空间复杂度:O(n^2) dp切片的内存
*/
func maxCoins(nums []int) int {
	// 定义dp[i][j]表示(i,j)区间内戳气球的最大值,注意：这里是开区间，所以不包含i和j位置的气球
	// 则假设在戳(i,j)区间内的气球的过程中剩下的最后一个气球为k，则其实只戳了k左边和右边的气球，即戳了(i,k)和(k,j)两个区间的气球
	// 那么如果剩下的最后一个气球为k，则最终的最大值为 dp[i][k]+dp[k][j]+val[i]*k*val[j]
	// dp[i][j] = max(dp[i][k]+dp[k][j]+val[i]*k*val[j] k属于(i, j))
	n := len(nums)
	val := make([]int, n+2)
	// 初始化最两边的值为1,否则相乘到val[0]或val[n+1]时如果为0，则全为0
	val[0], val[n+1] = 1, 1
	for i := 1; i <= n; i++ {
		val[i] = nums[i-1]
	}

	dp := make([][]int, n+2)
	for i := range dp {
		dp[i] = make([]int, n+2)
	}

	// 区间动态规划
	// i的下限为0,j的上限为n+1
	for i := n - 1; i >= 0; i-- {
		for j := i + 2; j <= n+1; j++ {
			// k位于(i, j)区间，所以大于i小于j
			for k := i + 1; k < j; k++ {
				sum := val[i] * val[k] * val[j]
				dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+sum)
			}
		}
	}
	return dp[0][n+1]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
